# 设计一个算法收集某些股票的每日报价，并返回该股票当日价格的 跨度 。 
# 
#  当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。 
# 
#  
#  例如，如果未来 7 天股票的价格是 [100,80,60,70,60,75,85]，那么股票跨度将是 [1,1,1,2,1,4,6] 。 
#  
# 
#  实现 StockSpanner 类： 
# 
#  
#  StockSpanner() 初始化类对象。 
#  int next(int price) 给出今天的股价 price ，返回该股票当日价格的 跨度 。 
#  
# 
#  
# 
#  示例： 
# 
#  
# 输入：
# ["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
# [[], [100], [80], [60], [70], [60], [75], [85]]
# 输出：
# [null, 1, 1, 1, 2, 1, 4, 6]
# 
# 解释：
# StockSpanner stockSpanner = new StockSpanner();
# stockSpanner.next(100); // 返回 1
# stockSpanner.next(80);  // 返回 1
# stockSpanner.next(60);  // 返回 1
# stockSpanner.next(70);  // 返回 2
# stockSpanner.next(60);  // 返回 1
# stockSpanner.next(75);  // 返回 4 ，因为截至今天的最后 4 个股价 (包括今天的股价 75) 都小于或等于今天的股价。
# stockSpanner.next(85);  // 返回 6
#  
# 
#  
# 
#  提示： 
# 
#  
#  1 <= price <= 10⁵ 
#  最多调用 next 方法 10⁴ 次 
#  
# 
#  Related Topics 栈 设计 数据流 单调栈 👍 478 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
class StockSpanner:
    """
    方法1：单调递减栈（栈底到栈顶是严格单调递减的）

    def __init__(self):
        self.stack = []
        self.index = -1

    def next(self, price: int) -> int:
        # 给加入的元素赋一个索引
        self.index += 1
        span = 0
        # 弹出栈内所有比当前price小（或者相等）的元素,那么留下的就是比当前元素大的元素了，且在栈顶
        while self.stack and price >= self.stack[-1][0]:
            self.stack.pop()
        # 栈为空就代表之前存的都比当前元素小，也就是左边没有比当前元素大的元素了
        if not self.stack:
            span = self.index + 1
        # 小的元素都弹出去了，栈顶的元素一定是第一个比当前元素大的元素
        else:
            span = self.index - self.stack[-1][1]

        self.stack.append((price, self.index))

        return span
        """

    """
    方法2：还是单调递减栈（栈底到栈顶是严格单调递减的），但是直接把跨度带入span
    """

    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        span = 1
        # 弹出栈内所有比当前price小（或者相等）的元素,那么留下的就是比当前元素大的元素了，且在栈顶
        while self.stack and price >= self.stack[-1][0]:
            # 这一步十分关键，注意，累加的是栈顶元素的span，而不是累加1
            span += self.stack.pop()[1]
        self.stack.append((price, span))

        return span


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)
# leetcode submit region end(Prohibit modification and deletion)
obj = StockSpanner()
print(obj.next(100), end='  ')
print(obj.next(80), end='  ')
print(obj.next(60), end='  ')
print(obj.next(70), end='  ')
print(obj.next(60), end='  ')
print(obj.next(75), end='  ')
print(obj.next(85), end='  ')

